class Solution {
    public int nthUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] arr = new int[n];
        arr[0] = 1;
        int next = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        while (next < n) {
            int min = Math.min(Math.min(arr[p2] * 2, arr[p3] * 3), arr[p5] * 5);
            arr[next] = min;
            while (arr[p2] * 2 <= min) {
                ++p2;
            }
            while (arr[p3] * 3 <= min) {
                ++p3;
            }
            while (arr[p5] * 5 <= min) {
                ++p5;
            }
            ++next;
        }
        return arr[next - 1];
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int res = s.nthUglyNumber(10);
        System.out.println(res);
    }
}